from numpy import *
import time

# calculate Euclidean distance
def euclDistance(vector1, vector2):
    return sqrt(sum(power(vector2 - vector1, 2)))


# init centroids with random samples
def initCentroids(dataSet, k):
    numSamples, dim = dataSet.shape
    # print numSamples,dim   12,1
    centroids = zeros((k, dim))
    # print centroids
    #set the first sample point
    index = int(random.uniform(0, numSamples))
    # print(index)
    # print(dataSet[index, :] ,centroids[i, :])
    centroids[0, :] = dataSet[index, :]
    list_dis = []
    for i in range(numSamples):
        dis=euclDistance(centroids[0, :],dataSet[i, :])
        list_dis.append(power(dis,2))
    list_pro = []
    # print(list_dis)
    for i in range(len(list_dis)):
        list_p =  list_dis[i]/sum(list_dis)
        list_pro.append(list_p)
    # print list_pro
    # print sum(list_pro)
    list_prosum = []
    list_prosum.append(list_pro[0])
    for i in range(1,len(list_pro)):
        list_prosum.append(list_prosum[i-1]+list_pro[i])
    # print(list_prosum)
    ran = random.uniform(0, 1)
    # print ran
    index_two = 0
    for i in range(len(list_prosum)-1):
        if ran >= list_prosum[i] and  ran < list_prosum[i+1]:
            index_two =  i+1
            break
        else:  index_two = 0
    # print(index_two)
    centroids[1, :] = dataSet[index_two, :]
    # print centroids
    return centroids


# k-means cluster
def kmeans(dataSet, k):
    numSamples = dataSet.shape[0]
    # print numSamples
    # first column stores which cluster this sample belongs to,
    # second column stores the eucl between this sample and its centroid
    clusterAssment = mat(zeros((numSamples, 2)))
    # print clusterAssment
    clusterChanged = True

    ##init centroids
    centroids = initCentroids(dataSet, k)  # select initial points

    while clusterChanged:
        clusterChanged = False
        ## for each sample
        # print(xrange(numSamples))
        for i in xrange(numSamples):
            minDist = 100000.0
            minIndex = 0
            ## for each centroid
            ## ind the centroid who is closest
            for j in range(k):
                # print(j,i)
                distance = euclDistance(centroids[j, :], dataSet[i, :])
                # print distance
                # print ("29384")
                if distance < minDist:
                    minDist = distance
                    minIndex = j

                    ##update its cluster
            # print clusterAssment
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
                # print ("*****",minIndex)
                clusterAssment[i, :] = minIndex, minDist ** 2

                ## update centroids
        for j in range(k):
            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]
            # print pointsInCluster
            centroids[j, :] = mean(pointsInCluster, axis=0)

            ##cluster complete
    # print centroids
    # print clusterAssment
    return centroids, clusterAssment


def runfromfile(dir, k=2):
    ## load data
    dataSet = []
    fileIn = open(dir)
    for line in fileIn.readlines():
        dataSet.append(float(line))

        ## clustering...
    dataSet = mat(dataSet).T
    # print dataSet
    # k = 2
    centroids, clusterAssment = kmeans(dataSet, k)
    return clusterAssment


def run(dataSet, k=2):
    # print "----------------------run kmeans------------------\n"
    # dataSet = rttDiff.testdiff()
    dataSet = mat(dataSet).T
    # print dataSet
    # k = 2
    centroids, clusterAssment = kmeans(dataSet, k)
    return clusterAssment


if __name__ == "__main__":
    # runfromfile('/home/zxg/scandir/sandwichlog.txt',2)
    A = [0.7585763931274414, 0.8314967155456543, 0.8880138397216797, 0.8885025978088379, 0.9186863899230957,
         1.6231417655944824, 1.6403794288635254, 1.6445517539978027, 1.80739164352417, 1.8272995948791504,
         1.8358826637268066, 1.9417881965637207]
    print(run(A, 2))
'''
if __name__ == "__main__":
    ## load data  
    dataSet = []  
    fileIn = open('/home/zxg/scandir/log.txt')  
    for line in fileIn.readlines():  
        dataSet.append(float(line)) 

    ## clustering...   
    dataSet = mat(dataSet).T
    #print dataSet  
    k = 2  
    centroids, clusterAssment = kmeans(dataSet, k)
'''
